SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Dynamic array</title>

</head>

Dynamic array

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a <a href="Random_access" title="Random access">random access</a>, variable-size <a href="List_data_structure" class="mw-redirect" title="List data structure">list data structure</a> that allows elements to be added or removed. It is supplied with <a href="Standard_libraries" class="mw-redirect" title="Standard libraries">standard libraries</a> in many modern mainstream <a href="Programming_language" title="Programming language">programming languages</a>. Dynamic arrays overcome a limit of static <a href="Array_data_type" class="mw-redirect" title="Array data type">arrays</a>, which have a fixed capacity that needs to be specified at <a href="Memory_management" title="Memory management">allocation</a>.

A dynamic array is not the same thing as a <a href="Dynamic_memory_allocation" class="mw-redirect" title="Dynamic memory allocation">dynamically allocated</a> array or <a href="Variable-length_array" title="Variable-length array">variable-length array</a>, either of which is an array whose size is fixed when the array is allocated, although a dynamic array may use such a fixed-size array as a back end.<a href="#cite_note-java_util_ArrayList-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Bounded-size_dynamic_arrays_and_capacity">Bounded-size dynamic arrays and capacity</h2></div>

A simple dynamic array can be constructed by allocating an array of fixed-size, typically larger than the number of elements immediately required. The elements of the dynamic array are stored contiguously at the start of the underlying array, and the remaining positions towards the end of the underlying array are reserved, or unused. Elements can be added at the end of a dynamic array in <a href="Time_complexity#Constant_time" title="Time complexity">constant time</a> by using the reserved space, until this space is completely consumed. When all space is consumed, and an additional element is to be added, then the underlying fixed-size array needs to be increased in size. Typically resizing is expensive because it involves allocating a new underlying array and copying each element from the original array. Elements can be removed from the end of a dynamic array in constant time, as no resizing is required. The number of elements used by the dynamic array contents is its logical size or size, while the size of the underlying array is called the dynamic array's capacity or physical size, which is the maximum possible size without relocating data.<a href="#cite_note-2">[2]</a>

A fixed-size array will suffice in applications where the maximum logical size is fixed (e.g. by specification), or can be calculated before the array is allocated. A dynamic array might be preferred if:

<ul><li>the maximum logical size is unknown, or difficult to calculate, before the array is allocated</li>

<li>it is considered that a maximum logical size given by a specification is likely to change</li>

<li>the amortized cost of resizing a dynamic array does not significantly affect performance or responsiveness</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Geometric_expansion_and_amortized_cost">Geometric expansion and amortized cost</h2></div>

To avoid incurring the cost of resizing many times, dynamic arrays resize by a large amount, such as doubling in size, and use the reserved space for future expansion. The operation of adding an element to the end might work as follows:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>function insertEnd(dynarray a, element e)

if (a.size == a.capacity)

// resize a to twice its current capacity:

a.capacity ← a.capacity * 2

// (copy the contents to the new memory location here)

a[a.size] ← e

a.size ← a.size + 1

</pre></div>

As n elements are inserted, the capacities form a <a href="Geometric_progression" title="Geometric progression">geometric progression</a>. Expanding the array by any constant proportion a ensures that inserting n elements takes <a href="Big_O_notation" title="Big O notation">O(n)</a> time overall, meaning that each insertion takes <a href="Amortized_analysis" title="Amortized analysis">amortized</a> constant time. Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity. This threshold must be strictly smaller than 1/a in order to provide <a href="Hysteresis" title="Hysteresis">hysteresis</a> (provide a stable band to avoid repeatedly growing and shrinking) and support mixed sequences of insertions and removals with amortized constant cost.

Dynamic arrays are a common example when teaching <a href="Amortized_analysis" title="Amortized analysis">amortized analysis</a>.<a href="#cite_note-gt-ad-3">[3]</a><a href="#cite_note-clrs-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Growth_factor">Growth factor</h2></div>

The growth factor for the dynamic array depends on several factors including a space-time trade-off and algorithms used in the memory allocator itself. For growth factor a, the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n. If memory allocator uses a <a href="First_fit_algorithm" class="mw-redirect" title="First fit algorithm">first-fit allocation</a> algorithm, then growth factor values such as a=2 can cause dynamic array expansion to run out of memory even though a significant amount of memory may still be available.<a href="#cite_note-:0-5">[5]</a> There have been various discussions on ideal growth factor values, including proposals for the <a href="Golden_ratio" title="Golden ratio">golden ratio</a> as well as the value 1.5.<a href="#cite_note-6">[6]</a> Many textbooks, however, use a = 2 for simplicity and analysis purposes.<a href="#cite_note-gt-ad-3">[3]</a><a href="#cite_note-clrs-4">[4]</a>

Below are growth factors used by several popular implementations:

<th>Implementation

</th>

<th>Growth factor (a)

</th></tr>

<tr>

<td>Java ArrayList<a href="#cite_note-java_util_ArrayList-1">[1]</a>

</td>

<td>1.5 (3/2)

</td></tr>

<tr>

<td><a href="Python_(programming_language)" title="Python (programming language)">Python</a> PyListObject<a href="#cite_note-7">[7]</a>

</td>

<td>~1.125 (n + (n >> 3))

</td></tr>

<tr>

<td><a href="Microsoft_Visual_C%2B%2B" title="Microsoft Visual C++">Microsoft Visual C++</a> 2013<a href="#cite_note-8">[8]</a>

</td>

<td>1.5 (3/2)

</td></tr>

<tr>

</td>

<td>2

</td></tr>

<tr>

<td><a href="Clang" title="Clang">Clang</a> 3.6<a href="#cite_note-:0-5">[5]</a>

</td>

<td>2

</td></tr>

<tr>

<td>Facebook folly/FBVector<a href="#cite_note-9">[9]</a>

</td>

<td>1.5 (3/2)

</td></tr>

<tr>

<td><a href="Unreal_Engine" title="Unreal Engine">Unreal Engine</a> TArray<a href="#cite_note-10">[10]</a>

</td>

<td>~1.375 (n + ((3 * n) >> 3))

</td></tr>

<tr>

</td>

<td>2

</td></tr>

<tr>

<td><a href="Go_(programming_language)" title="Go (programming language)">Go</a> slices<a href="#cite_note-12">[12]</a>

</td>

<td>between 1.25 and 2

</td></tr>

<tr>

<td><a href="Nim_(programming_language)" title="Nim (programming language)">Nim</a> sequences<a href="#cite_note-13">[13]</a>

</td>

<td>2

</td></tr>

<tr>

<td><a href="Steel_Bank_Common_Lisp" title="Steel Bank Common Lisp">SBCL</a> (<a href="Common_Lisp" title="Common Lisp">Common Lisp</a>) vectors<a href="#cite_note-14">[14]</a>

</td>

<td>2

</td></tr>

<tr>

<td><a href="C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a> (<a href=".NET" title=".NET">.NET</a> 8) List

</td>

<td>2

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Performance">Performance</h2></div>

<caption>Comparison of list data structures

</caption>

</th>

<th rowspan="2">Peek (index)

</th>

<th colspan="3">Mutate (insert or delete) at …

</th>

<th rowspan="2">Excess space, average

</th></tr>

<tr>

<th>Beginning

</th>

<th>End

</th>

<th>Middle

</th></tr>

<tr>

<td><a href="Linked_list" title="Linked list">Linked list</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1), known end element; Θ(n), unknown end element

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td></tr>

<tr>

<td><a href="Array_data_structure" class="mw-redirect" title="Array data structure">Array</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td data-sort-value="" style="background: var(--background-color-interactive, #ececec); color: var(--color-base, inherit); vertical-align: middle; text-align: center;" class="table-na">—

</td>

<td data-sort-value="" style="background: var(--background-color-interactive, #ececec); color: var(--color-base, inherit); vertical-align: middle; text-align: center;" class="table-na">—

</td>

<td data-sort-value="" style="background: var(--background-color-interactive, #ececec); color: var(--color-base, inherit); vertical-align: middle; text-align: center;" class="table-na">—

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">0

</td></tr>

<tr>

<td>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1) <a href="Amortized_analysis" title="Amortized analysis">amortized</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td>

</td></tr>

<tr>

<td><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Balanced tree</a>

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log n)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log n)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log n)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log n)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td></tr>

<tr>

<td>Random-access list

</td>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

</td>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td></tr>

<tr>

<td><a href="Hashed_array_tree" title="Hashed array tree">Hashed array tree</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1) <a href="Amortized_analysis" title="Amortized analysis">amortized</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(n)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(√n)

</td></tr></tbody></table>

The dynamic array has performance similar to an array, with the addition of new operations to add and remove elements:

<ul><li>Getting or setting the value at a particular index (constant time)</li>

<li>Iterating over the elements in order (linear time, good cache performance)</li>

<li>Inserting or deleting an element in the middle of the array (linear time)</li>

<li>Inserting or deleting an element at the end of the array (constant amortized time)</li></ul>

Dynamic arrays benefit from many of the advantages of arrays, including good <a href="Locality_of_reference" title="Locality of reference">locality of reference</a> and <a href="Data_cache" class="mw-redirect" title="Data cache">data cache</a> utilization, compactness (low memory use), and <a href="Random_access" title="Random access">random access</a>. They usually have only a small fixed additional overhead for storing information about the size and capacity. This makes dynamic arrays an attractive tool for building <a href="Cache_(computing)" title="Cache (computing)">cache</a>-friendly <a href="Data_structure" title="Data structure">data structures</a>. However, in languages like Python or Java that enforce reference semantics, the dynamic array generally will not store the actual data, but rather it will store <a href="Reference_(computer_science)" title="Reference (computer science)">references</a> to the data that resides in other areas of memory. In this case, accessing items in the array sequentially will actually involve accessing multiple non-contiguous areas of memory, so the many advantages of the cache-friendliness of this data structure are lost.

Compared to <a href="Linked_list" title="Linked list">linked lists</a>, dynamic arrays have faster indexing (constant time versus linear time) and typically faster iteration due to improved locality of reference; however, dynamic arrays require linear time to insert or delete at an arbitrary location, since all following elements must be moved, while linked lists can do this in constant time. This disadvantage is mitigated by the <a href="Gap_buffer" title="Gap buffer">gap buffer</a> and tiered vector variants discussed under Variants below. Also, in a highly <a href="Fragmentation_(computer)" class="mw-redirect" title="Fragmentation (computer)">fragmented</a> memory region, it may be expensive or impossible to find contiguous space for a large dynamic array, whereas linked lists do not require the whole data structure to be stored contiguously.

A <a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">balanced tree</a> can store a list while providing all operations of both dynamic arrays and linked lists reasonably efficiently, but both insertion at the end and iteration over the list are slower than for a dynamic array, in theory and in practice, due to non-contiguous storage and tree traversal/manipulation overhead.

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

<a href="Gap_buffer" title="Gap buffer">Gap buffers</a> are similar to dynamic arrays but allow efficient insertion and deletion operations clustered near the same arbitrary location. Some <a href="Deque" class="mw-redirect" title="Deque">deque</a> implementations use <a href="Deque" class="mw-redirect" title="Deque">array deques</a>, which allow amortized constant time insertion/removal at both ends, instead of just one end.

Goodrich<a href="#cite_note-17">[17]</a> presented a dynamic array algorithm called tiered vectors that provides O(n1/k) performance for insertions and deletions from anywhere in the array, and O(k) get and set, where k ≥ 2 is a constant parameter.

<a href="Hashed_array_tree" title="Hashed array tree">Hashed array tree</a> (HAT) is a dynamic array algorithm published by Sitarski in 1996.<a href="#cite_note-sitarski96-18">[18]</a> Hashed array tree wastes order n1/2 amount of storage space, where n is the number of elements in the array. The algorithm has O(1) amortized performance when appending a series of objects to the end of a hashed array tree.

In a 1999 paper,<a href="#cite_note-brodnik-19">[19]</a> Brodnik et al. describe a tiered dynamic array data structure, which wastes only n1/2 space for n elements at any point in time, and they prove a lower bound showing that any dynamic array must waste this much space if the operations are to remain amortized constant time. Additionally, they present a variant where growing and shrinking the buffer has not only amortized but worst-case constant time.

Bagwell (2002)<a href="#cite_note-20">[20]</a> presented the VList algorithm, which can be adapted to implement a dynamic array.

Naïve resizable arrays -- also called "the worst implementation" of resizable arrays -- keep the allocated size of the array exactly big enough for all the data it contains, perhaps by calling <a href="Realloc" class="mw-redirect" title="Realloc">realloc</a> for each and every item added to the array. Naïve resizable arrays are the simplest way of implementing a resizable array in C. They don't waste any memory, but appending to the end of the array always takes Θ(n) time.<a href="#cite_note-sitarski96-18">[18]</a><a href="#cite_note-21">[21]</a><a href="#cite_note-22">[22]</a><a href="#cite_note-23">[23]</a><a href="#cite_note-24">[24]</a>

Linearly growing arrays pre-allocate ("waste") Θ(1) space every time they re-size the array, making them many times faster than naïve resizable arrays -- appending to the end of the array still takes Θ(n) time but with a much smaller constant.

Naïve resizable arrays and linearly growing arrays may be useful when a space-constrained application needs lots of small resizable arrays;

they are also commonly used as an educational example leading to exponentially growing dynamic arrays.<a href="#cite_note-25">[25]</a>

<div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2></div>

<a href="C%2B%2B" title="C++">C++</a>'s <a href="Vector_(C%2B%2B)" class="mw-redirect" title="Vector (C++)"><code>std::vector</code></a> and <a href="Rust_(programming_language)" title="Rust (programming language)">Rust</a>'s <code>std::vec::Vec</code> are implementations of dynamic arrays, as are the <code>ArrayList</code><a href="#cite_note-26">[26]</a> classes supplied with the <a href="Java_(programming_language)" title="Java (programming language)">Java</a> API<a href="#cite_note-Bloch-27">[27]</a>: 236 and the <a href=".NET_Framework" title=".NET Framework">.NET Framework</a>.<a href="#cite_note-28">[28]</a><a href="#cite_note-Skeet-29">[29]</a>: 22

The generic <code>List<></code> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays. <a href="Smalltalk" title="Smalltalk">Smalltalk</a>'s <code>OrderedCollection</code> is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1).

<a href="Python_(Programming_Language)" class="mw-redirect" title="Python (Programming Language)">Python</a>'s <code>list</code> datatype implementation is a dynamic array the growth pattern of which is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...<a href="#cite_note-30">[30]</a>

<a href="Delphi_(programming_language)" class="mw-redirect" title="Delphi (programming language)">Delphi</a> and <a href="D_(programming_language)" title="D (programming language)">D</a> implement dynamic arrays at the language's core.

<a href="Ada_(programming_language)" title="Ada (programming language)">Ada</a>'s <a href="https://en.wikibooks.org/wiki/Ada_Programming/Libraries/Ada.Containers.Vectors" class="extiw external" title="wikibooks:Ada Programming/Libraries/Ada.Containers.Vectors"><code>Ada.Containers.Vectors</code></a> generic package provides dynamic array implementation for a given subtype.

Many scripting languages such as <a href="Perl" title="Perl">Perl</a> and <a href="Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a> offer dynamic arrays as a built-in <a href="Primitive_data_type" title="Primitive data type">primitive data type</a>.

Several cross-platform frameworks provide dynamic array implementations for <a href="C_(programming_language)" title="C (programming language)">C</a>, including <code>CFArray</code> and <code>CFMutableArray</code> in <a href="Core_Foundation" title="Core Foundation">Core Foundation</a>, and <code>GArray</code> and <code>GPtrArray</code> in <a href="GLib" title="GLib">GLib</a>.

<a href="Common_Lisp" title="Common Lisp">Common Lisp</a> provides a rudimentary support for resizable vectors by allowing to configure the built-in <code>array</code> type as adjustable and the location of insertion by the fill-pointer.

<ul><li><a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">Stack (data structure)</a></li>

<li><a href="Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">Queue (data structure)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<li id="cite_note-java_util_ArrayList-1">^ <a href="#cite_ref-java_util_ArrayList_1-0">a</a> <a href="#cite_ref-java_util_ArrayList_1-1">b</a> See, for example, the <a rel="nofollow" class="external text" href="http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/e0e25ac28560/src/share/classes/java/util/ArrayList.java">source code of java.util.ArrayList class from OpenJDK 6</a>.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLambert,_Kenneth_Alfred2009" class="citation cs2">Lambert, Kenneth Alfred (2009), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=VtfM3YGW5jYC&q=%22logical+size%22+%22dynamic+array%22&pg=PA518">"Physical size and logical size"</a>, Fundamentals of Python: From First Programs Through Data Structures, Cengage Learning, p. 510, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1423902188</bdi></cite>

</li>

<li id="cite_note-gt-ad-3">^ <a href="#cite_ref-gt-ad_3-0">a</a> <a href="#cite_ref-gt-ad_3-1">b</a> <cite id="CITEREFGoodrichTamassia2002" class="citation cs2"><a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; <a href="Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a> (2002), "1.5.2 Analyzing an Extendable Array Implementation", Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39–41</cite>.

</li>

<li id="cite_note-clrs-4">^ <a href="#cite_ref-clrs_4-0">a</a> <a href="#cite_ref-clrs_4-1">b</a> <cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2001) [1990]. "17.4 Dynamic tables". <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a> (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>.</cite>

</li>

<li id="cite_note-:0-5">^ <a href="#cite_ref-:0_5-0">a</a> <a href="#cite_ref-:0_5-1">b</a> <a href="#cite_ref-:0_5-2">c</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20150806162750/http://www.gahcep.com/cpp-internals-stl-vector-part-1/">"C++ STL vector: definition, growth factor, member functions"</a>. Archived from <a rel="nofollow" class="external text" href="http://www.gahcep.com/cpp-internals-stl-vector-part-1/">the original</a> on 2015-08-06. Retrieved 2015-08-05.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://arquivo.pt/wayback/20110122130054/https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D">"vector growth factor of 1.5"</a>. comp.lang.c++.moderated. Google Groups. Archived from <a rel="nofollow" class="external text" href="https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D">the original</a> on 2011-01-22. Retrieved 2015-08-05.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a rel="nofollow" class="external text" href="https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58">List object implementation</a> from github.com/python/cpython/, retrieved 2020-03-23.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFBrais2013" class="citation web cs1">Brais, Hadi (15 November 2013). <a rel="nofollow" class="external text" href="https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/">"Dissecting the C++ STL Vector: Part 3 - Capacity & Size"</a>. Micromysteries. Retrieved 2015-08-05.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md">"facebook/folly"</a>. GitHub. Retrieved 2015-08-05.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://forums.unrealengine.com/t/nested-tarrays-in-structs-and-memory/2357416/3">"Nested TArrays in structs and memory"</a>. Epic Developer Community Forums. 2025-02-26. Retrieved 2025-05-26.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/rust-lang/rust/blob/fd4b177aabb9749dfb562c48e47379cea81dc277/src/liballoc/raw_vec.rs#L443">"rust-lang/rust"</a>. GitHub. Retrieved 2020-06-09.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/golang/go/blob/master/src/runtime/slice.go#L188">"golang/go"</a>. GitHub. Retrieved 2021-09-14.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://zevv.nl/nim-memory/#_growing_a_seq">"The Nim memory model"</a>. zevv.nl. Retrieved 2022-05-24.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/sbcl/sbcl/blob/master/src/code/array.lisp#L1200-L1204">"sbcl/sbcl"</a>. GitHub. Retrieved 2023-02-15.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBrodnikCarlssonSedgewickMunro1999" class="citation cs2">Brodnik, Andrej; Carlsson, Svante; <a href="Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Munro, JI; Demaine, ED (1999), <a rel="nofollow" class="external text" href="http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf">Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09)</a> (PDF), Department of Computer Science, University of Waterloo</cite>

</li>

<li id="cite_note-okasakiComparison-16">^ <a href="#cite_ref-okasakiComparison_16-0">a</a> <a href="#cite_ref-okasakiComparison_16-1">b</a> <a href="#cite_ref-okasakiComparison_16-2">c</a> <cite id="CITEREFChris_Okasaki1995" class="citation journal cs1">Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F224164.224187">10.1145/224164.224187</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFGoodrichKloss_II1999" class="citation cs2"><a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; Kloss II, John G. (1999), <a rel="nofollow" class="external text" href="https://archive.org/details/algorithmsdatast0000wads/page/205">"Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences"</a>, <a href="Workshop_on_Algorithms_and_Data_Structures" class="mw-redirect" title="Workshop on Algorithms and Data Structures">Workshop on Algorithms and Data Structures</a>, Lecture Notes in Computer Science, 1663: <a rel="nofollow" class="external text" href="https://archive.org/details/algorithmsdatast0000wads/page/205">205–216</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-48447-7_21">10.1007/3-540-48447-7_21</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-66279-2</bdi></cite>

</li>

<li id="cite_note-sitarski96-18">^ <a href="#cite_ref-sitarski96_18-0">a</a> <a href="#cite_ref-sitarski96_18-1">b</a> <cite id="CITEREFSitarski1996" class="citation cs2">Sitarski, Edward (September 1996), <a rel="nofollow" class="external text" href="http://www.ddj.com/architect/184409965?pgno=5">"HATs: Hashed array trees"</a>, Algorithm Alley, Dr. Dobb's Journal, 21 (11)</cite>

</li>

<li id="cite_note-brodnik-19"><a href="#cite_ref-brodnik_19-0">^</a> <cite id="CITEREFBrodnikCarlssonSedgewickMunro1999" class="citation cs2">Brodnik, Andrej; Carlsson, Svante; <a href="Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Munro, JI; Demaine, ED (1999), <a rel="nofollow" class="external text" href="http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf">Resizable Arrays in Optimal Time and Space</a> (PDF) (Technical Report CS-99-09), Department of Computer Science, University of Waterloo</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFBagwell2002" class="citation cs2">Bagwell, Phil (2002), <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/bagwell02fast.html">Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays</a>, EPFL</cite>

</li>

Mike Lam.

<a rel="nofollow" class="external text" href="https://w3.cs.jmu.edu/lam2mo/cs240_2015_08/files/04-dyn_arrays.pdf">"Dynamic Arrays"</a>.

</li>

<a rel="nofollow" class="external text" href="https://users.cs.northwestern.edu/~jesse/course/cs214-fa19/lec/17-amortized.pdf">"Amortized Time"</a>.

</li>

<a rel="nofollow" class="external text" href="https://iq.opengenus.org/hashed-array-tree/">"Hashed Array Tree: Efficient representation of Array"</a>.

</li>

<a rel="nofollow" class="external text" href="https://people.ksp.sk/~kuko/gnarley-trees/Complexity2.html">"Different notions of complexity"</a>.

</li>

Peter Kankowski.

<a rel="nofollow" class="external text" href="https://www.strchr.com/dynamic_arrays">"Dynamic arrays in C"</a>.

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> Javadoc on <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/ArrayList.html">ArrayList</a></code>

</li>

<li id="cite_note-Bloch-27"><a href="#cite_ref-Bloch_27-0">^</a> <cite id="CITEREFBloch2018" class="citation book cs1">Bloch, Joshua (2018). "Effective Java: Programming Language Guide" (third ed.). Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0134685991</bdi>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <a rel="nofollow" class="external text" href="https://msdn.microsoft.com/en-us/library/system.collections.arraylist">ArrayList Class</a>

</li>

<li id="cite_note-Skeet-29"><a href="#cite_ref-Skeet_29-0">^</a> <cite id="CITEREFSkeet2019" class="citation book cs1">Skeet, Jon (23 March 2019). C# in Depth. Manning. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1617294532</bdi>.</cite>

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <a rel="nofollow" class="external text" href="https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58">listobject.c (github.com)</a>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/dynamicarray.html">NIST Dictionary of Algorithms and Data Structures: Dynamic array</a></li>

<li><a rel="nofollow" class="external text" href="http://www.bsdua.org/libbsdua.html#vpool">VPOOL</a> - C language implementation of dynamic array.</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20090704095801/http://www.collectionspy.com/">CollectionSpy</a> — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.</li>

<li><a rel="nofollow" class="external text" href="http://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html">Open Data Structures - Chapter 2 - Array-Based Lists</a>, <a href="Pat_Morin" title="Pat Morin">Pat Morin</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li>

<li><a href="Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Associative_array" title="Associative array">Associative array</a>

<ul><li><a href="Multimap" title="Multimap">Multimap</a></li>

<li><a href="Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a>

<ul><li><a href="Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li>

<li><a href="Priority_queue" title="Priority queue">Priority queue</a>

<ul><li><a href="Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li>

<ul><li><a href="Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li>

<li><a href="Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bit_array" title="Bit array">Bit array</a></li>

<li><a href="Circular_buffer" title="Circular buffer">Circular buffer</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li>

<li><a href="Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Association_list" title="Association list">Association list</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li>

<li><a href="XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>

<li><a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay tree</a></li></ul></li>

<ul><li><a href="Binary_heap" title="Binary heap">Binary heap</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial heap</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li>

<li><a href="Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-26" href="https://en.wikipedia.org/wiki/?title=Dynamic_array&oldid=1292303927">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>